
class Solution {
public:
    ListNode*mergetwolists(ListNode* l1,ListNode *l2)
    {
        if(l1==nullptr)return l2;
        if(l2==nullptr)return l1;
        ListNode*head=new ListNode(0);
        ListNode*tail=head;
        while(l1&&l2)
        {
        if(l1->val<l2->val)
        {
            tail->next=l1;
            l1=l1->next;
            
        }
        else
        {
           tail->next=l2;
           l2=l2->next;
        }
           tail=tail->next;
        }
        tail->next=l1?l1:l2;
        return head->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* newnode=nullptr;
        for(int i=0;i<lists.size();i++)
        {
            newnode=mergetwolists(newnode,lists[i]);
        }
        return newnode;
    }
};